﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace bg
{
  public static class ListUtils
  {
    public static float Average(this IEnumerable<float> l)
    {
      return l.Sum() / (float)l.Count();
    }

    public static IEnumerable<float> FixSign(this IEnumerable<float> l)
    {
      float min = l.Min();
      if (min < 0)
      {
        return l.Select(f => f - min).ToList();
      }
      else
      {
        return l;
      }
    }

    public static T Roulette<T>(this IList<T> l, Func<T, float> scoreFunc)
    {
      IList<float> scores = l.Select(scoreFunc).FixSign().ToList();
      float totalScore = scores.Sum();
      if (totalScore == 0)
      {
        return l[new Random().Next(l.Count)];
      }
      float targetScore = (float)new Random().NextDouble() * totalScore;
      float score = 0;
      int i = 0;
      while (score < targetScore)
      {
        score += scores[i++];
      }
      return l[i - 1];
    }

    public static void Add<T>(this IList<T> l, IEnumerable<T> r)
    {
      foreach (T t in r)
      {
        l.Add(t);
      }
    }

    public static T MaxBy<T, U>(this IEnumerable<T> l, Func<T, U> f)
    {
      return l.OrderByDescending(f).First();
    }
  }

  public class Game
  {
    public Game(IDictionary<int, string> types, IDictionary<string, Func<GameState, GameState>> moves)
    {
      this.types = types;
      this.moves = moves;
      if (this.moves == null)
      {
        this.moves = new Dictionary<string, Func<GameState, GameState>>();
      }
      this.moves["console"] = new Func<GameState, GameState>(console);
      this.moves["max"] = new Func<GameState, GameState>(max);
      this.moves["search"] = new Func<GameState, GameState>(search);
    }

    public GameState Run(GameState state)
    {
      while (state.GetWinner() == 0)
      {
        int player = state.GetPlayer();
        System.Diagnostics.Debug.Assert(types.ContainsKey(player));
        string type = types[player];
        System.Diagnostics.Debug.Assert(moves.ContainsKey(type));
        Func<GameState, GameState> move = moves[type];
        state = move(state);
      }
      return state;
    }

    private GameState console(GameState state)
    {
      System.Console.WriteLine("current state:");
      System.Console.Write(state);
      IList<GameMove> moves = state.Expand();
      for (int i = 0; i < moves.Count; ++i)
      {
        System.Console.WriteLine(string.Format("{0}: {1}", i, moves[i]));
      }
      string line = System.Console.ReadLine();
      int index = int.Parse(line);
      GameMove move = moves[index];
      return state.Apply(move);
    }

    private IList<float> collectScores(GameState state, int player, int ply)
    {
      IList<float> scores = new List<float>();
      scores.Add(state.Eval(player));
      if (state.GetWinner() == 0 && ply > 0)
      {
        foreach (GameMove move in state.Expand())
        {
          foreach (float score in collectScores(state.Apply(move), player, ply - 1))
          {
            scores.Add(score);
          }
        }
      }
      return scores;
    }

    private GameState max(GameState state)
    {
      return state.Expand().Select(move => state.Apply(move)).OrderByDescending(child => collectScores(child, state.GetPlayer(), 2).Average()).First();
    }

    private IDictionary<int, string> types;

    private IDictionary<string, Func<GameState, GameState>> moves;

    private class GameTree
    {
      public GameTree(GameState state)
      {
        this.state = state;
        expanded = false;
        children = new List<GameTree>();
        ply = 0;
        player = state.GetPlayer();
        score = state.Eval(player);
      }

      public GameTree(GameTree tree, GameState state)
      {
        this.state = state;
        expanded = false;
        children = new List<GameTree>();
        tree.children.Add(this);
        ply = tree.ply + 1;
        player = tree.player;
        score = this.state.Eval(player);
      }

      public IList<GameTree> GetNodes()
      {
        IList<GameTree> nodes = new List<GameTree>() { this };
        foreach (GameTree child in children)
        {
          nodes.Add(child.GetNodes());
        }
        return nodes;
      }

      public IList<GameTree> GetLeaves()
      {
        return GetNodes()
          .Where(node => !node.expanded)
          .ToList();
      }

      public void Expand()
      {
        if (!expanded)
        {
          expanded = true;
          if (state.GetWinner() == 0)
          {
            children.Add(state
              .Expand()
              .Select(move => state.Apply(move))
              .Select(child => new GameTree(this, child))
              .ToList());
          }
        }
      }

      public void ExpandFor(TimeSpan maxTime, int maxPly, Func<GameTree, float> scoreFunc)
      {
        IList<GameTree> stack = GetLeaves();
        DateTime start = DateTime.Now;
        while (DateTime.Now - start < maxTime && stack.Any())
        {
          GameTree node;
          if (scoreFunc != null)
          {
            node = stack.Roulette(scoreFunc);
          }
          else
          {
            node = stack.First();
          }
          stack.Remove(node);
          node.Expand();
          stack.Add(node.children.Where(child => child.ply < maxPly || maxPly <= 0));
        }
      }

      public GameState state;

      private bool expanded;

      public IList<GameTree> children;

      public int ply;

      private int player;

      public float score;
    }

    private GameState search(GameState state)
    {
      GameTree tree = new GameTree(state);
      tree.ExpandFor(TimeSpan.FromSeconds(1), 5, node => node.score);
      return tree.children
        .MaxBy(child => child
          .GetNodes()
          .Select(node => node.score)
          .Average()).state;
    }
  }
}
